package leetcode_core.leetcode_6;

import org.junit.Test;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月31日 17:55
 */
public class MergeSort {
    private int[] temp;
    private void merge(int[] nums,int lo,int mid,int hi){
        for(int i = lo;i<=hi;i++){
            temp[i] = nums[i];
        }
        int i = lo;
        int j = mid+1;
        //双指针法
        for(int p = lo; p<=hi; p++){
            if(i == mid+1){
                nums[p] = temp[j++];
            }else if(j == hi+1){
                nums[p] = temp[i++];
            }else if(temp[i] > temp[j]){
                nums[p] = temp[j++];
            }else{
                nums[p] = temp[i++];
            }
        }
    }

    private void sort(int[] nums,int lo,int hi){
        if(lo == hi){//当相等的时候就不需要再二分了
            return;
        }
        int mid = lo + ((hi-lo)>>1);
        //后序遍历
        sort(nums,lo,mid);
        sort(nums,mid+1,hi);
        merge(nums,lo,mid,hi);
    }

    public int[] sortArray(int[] nums){
        temp = new int[nums.length];
        sort(nums,0, nums.length-1);
        return nums;
    }

    @Test
    public void test(){
        sortArray(new int[]{4,3,2,1});
    }

}
